// 200. [DFS迷宫/深搜法]岛屿数量
// https://leetcode.cn/problems/number-of-islands/
// 给你一个由'1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
// 你可以假设该网格的四条边均被水包围。1 <= row, col <= 300, grid[i][j]值为0或1
// 输入：grid = [
// ["1","1","1","1","0"],
// ["1","1","0","1","0"],
// ["1","1","0","0","0"],
// ["0","0","0","0","0"]
// ]
// 输出：1
// 输入：grid = [
// ["1","1","0","0","0"],
// ["1","1","0","0","0"],
// ["0","0","1","0","0"],
// ["0","0","0","1","1"]
// ]
// 输出：3
// 方法一：深度优先搜索 复杂度：O(MN)
// 我们可以将二维网格看成一个无向图，竖直或水平相邻的 11
// 之间有边相连。为了求出岛屿的数量， 我们可以扫描整个二维网格。如果一个位置为
// 11，则以其为起始节点开始进行深度优先搜索。
// 在深度优先搜索的过程中，每个搜索到的 11 都会被重新标记为 00。
// 最终岛屿的数量就是我们进行深度优先搜索的次数。
class Solution {
 private:
  void dfs(vector<vector<char>>& grid, int r, int c) {
    int nr = grid.size();
    int nc = grid[0].size();
    grid[r][c] = '0';
    if (r - 1 >= 0 && grid[r - 1][c] == '1') dfs(grid, r - 1, c);
    if (r + 1 < nr && grid[r + 1][c] == '1') dfs(grid, r + 1, c);
    if (c - 1 >= 0 && grid[r][c - 1] == '1') dfs(grid, r, c - 1);
    if (c + 1 < nc && grid[r][c + 1] == '1') dfs(grid, r, c + 1);
  }

 public:
  int numIslands(vector<vector<char>>& grid) {
    if (grid.size() == 0) return 0;
    int num_islands = 0;
    for (int r = 0; r < grid.size(); ++r) {
      for (int c = 0; c < grid[0].size(); ++c) {
        if (grid[r][c] == '1') {
          ++num_islands;
          dfs(grid, r, c);
        }
      }
    }
    return num_islands;
  }
};